1. Field of the Invention
This invention relates to the field computer technology for mapping one data space to another data space.
2. Background
Computers are often used to map data that exists in a source data space to a destination data space. This type of mapping is often used in xe2x80x9cvirtual realityxe2x80x9d and xe2x80x9ctelepresencexe2x80x9d applications. The data in the source data space can represent a warped image that is obtained by a distorting lens such as a fisheye lens or a catadioptric lens. The data in the destination data space can be presented by a presentation device such as a video screen, computer monitor or printer. The problem is how to rapidly generate the data for the destination data space from the source data space.
One approach is to backward map the coordinates of a point in the destination data space to coordinates in the source data space and to obtain the value for the point in the destination data space from the mapped point in the source data space. Precisely mapping each point (for example, by using floating point calculations to perform the mapping) is expensive in either memory or computation, or both.
Another approach is to precisely map a grid of points from the destination data space to the source data space. These grid points bound regions (patches) that contain pixels that have similar mapping as the grid points that bound the region. Thus, the precisely mapped grid points are used to determine coefficients for a mapping that can be applied to each point in the region. Each of the grid points in the destination data space has a corresponding grid point in the source data space. Thus, the destination grid point and the corresponding source grid point are referred to as a xe2x80x9cpoint pair.xe2x80x9d
By using all four of the destination and source point pairs that bound a region, a perspective transformation can be computed and used to find the corresponding pixel in the source data space. Thus,                               x          s                =                                            ax              d                        +                          by              d                        +                          t              x                                                          ex              d                        +                          fy              d                        +            1                                                            y          s                =                                            cx              d                        +                          dy              d                        +                          t              y                                                          ex              d                        +                          fy              d                        +            1                              
Can be used to perform the mapping where (xs, ys) is the is the resulting coordinate in the source data space, (xd, yd) is the coordinates of the pixel in the destination data space, and a, b, c, d, e, f tx and ty are the perspective transform coefficients. This calculation includes at least six multiply operations, two division operations, and six add operations. The multiply and division operations are computationally expensive., Although this equation does not generate mapping artifacts between the regions, the additional computational overhead is often prohibitive.
Another approach is to generate a look-up table that provides the xs and ys coordinates when given the xd and yd coordinates. With high resolution images and high-resolution presentation devices, these look-up tables become unwieldy even with modem computers.
Another approach is to approximately map the region using a less computationally expensive formula. For example, an affine transformation can be used to perform this mapping. In this circumstance, three of the four sets of destination and source point pairs are used to compute the affine coefficients for the transformation. Then coordinates that specify a pixel that in the destination data space can be used to find the corresponding pixel in the source data space. Thus,
xs=axd+by+c 
ys=dxd+eyd+f 
Where (xs, ys) is the resulting coordinate in the source data space, (xd, yd) is the coordinates of the pixel in the destination data space, and a, b, c, d, e and f are the affine coefficients for the grid region bounded by the precisely mapped grid points. This calculation includes four multiply operations and four add operations for each pixel in the patch and so is still computationally expensive. An additional problem with this approach is that an affine transformation often generates a very poor approximation to the perspective transformation. The affine transformation only uses three of the four point pairs that bound the region. Thus, the affine transformation can generate mapping artifacts (such as discontinuities) along edges of the quadralateral defining the region in the source space.
FIG. 1A illustrates a quadralateral patch in source space, indicated by general reference character 100, used to show mapping artifacts generated by the affine transformation. The quadralateral patch in source space 100 is bounded by grid points (such as a point A 101, a point B 103, a point C 105, and a point D 107). Applying an affine transformation to this region (using the points 101, 103, and 105 and the corresponding points in the destination space) would generate the patch bounded by the point A 101, the point B 103, the point C 105 and a point Dxe2x80x2 109 instead of approximating the original patch.
FIG. 1B illustrates a presentation of a correctly mapped image, indicated by general reference character 150, that represents a magnified image presented on a presentation device. This image does not have any mapping artifacts. It can be generated by precisely mapping each point in the destination data space to the source data space. It can also be generated by precisely mapping grid points, and using the perspective transformation previously discussed to map the points in each region defined by the grid. Compare FIG. 1B with FIG. 1C.
FIG. 1C illustrates a presentation of an incorrectly mapped image, indicated by general reference character 160, that shows mapping artifacts 161 that can result from the use of the affine transformation. As can be seen, these mapping artifacts include discontinuities in lines. Other mapping artifacts include (without limitation) texture discontinuities and color discontinuities.
It would be advantageous to use a fast mapping algorithm that also provides a good approximation for a precise perspective-correct transformation that maintains continuity across patch boundaries without the computational or memory overheads associated with the prior art. Devices and computers that use these methods will operate more efficiently than those that use prior art methods will.
The invention provides a fast and accurate means of mapping one data space into another by precisely mapping grid points between the data spaces and then by performing a bilateral-bilinear interpolation to map the points bounded by the precisely mapped grid points.
One aspect of the invention is a computer-controlled method that includes the step of determining a region in a destination data space. The region is bounded by a plurality of grid points. It defines a first plurality of data points in the destination data space. The method precisely maps the plurality of grid points in the destination data space to a plurality of mapped grid points in a source data space. The source data space contains, or is associated with, a second plurality of data points. The plurality of mapped grid points define a plurality of boundary lines that represent the boundary of the region as mapped into the source data space. The method also applies a bilateral-bilinear interpolation algorithm to approximately map the first plurality of data points to the second plurality of data points.
Another aspect of the invention is an apparatus that includes a central processing unit (CPU) and a memory coupled to the CPU. The apparatus also includes a region determination mechanism that is configured to determine a region in a destination data space. The region is bounded by a plurality of grid points. The region defines a first plurality of data points within the destination data space. The apparatus also includes a precise mapping mechanism that is configured to precisely map the plurality of grid points determined by the region determination mechanism to a plurality of mapped grid points in a source data space. The source data space contains (or associates) a second plurality of data points. The plurality of mapped grid points define a plurality of boundary lines that represent the boundary of the region as mapped into the source data space. The apparatus also includes a bilateral-bilinear interpolation mechanism that is configured to approximately map the first plurality of data points in the region to the second plurality of data points using the plurality of mapped grid points.
Yet another aspect of the invention, is a computer program product that includes a computer usable storage medium having computer readable code embodied therein for causing a computer to map a destination data space to a source data space. When executed on a computer, the computer readable code causes the computer to effect a precise mapping mechanism, a region determination mechanism, and a bilateral-bilinear interpolation mechanism. Each of these mechanisms having the same functions as the corresponding mechanisms for the previously described apparatus.
Still another aspect of the invention is a computer program product embodied in a carrier wave transmitting computer readable code therein for causing a computer to map a destination data space to a source data space. When executed on a computer, the computer readable code causes the computer to effect a precise mapping mechanism, a region determination mechanism, and a bilateral-bilinear interpolation mechanism. Each of these mechanisms having the same functions as the corresponding mechanisms for the previously described apparatus.